﻿// poj3258 River Hopscotch.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
using namespace std;
/*


http://poj.org/problem?id=3258

河流跳格子
时间限制：2000MS 内存限制：65536K
总提交量。32480 已接受。13278
说明

牛群每年都会举办一个活动，其特点是采用一种奇特的跳房子的方式，即在河里小心翼翼地从一块石头跳到另一块石头。
激动人心的活动发生在一条长长的直河上，河的起点是一块石头，终点是另一块石头，离起点有L个单位（1≤L≤1,000,000）。
沿着起点和终点之间的河流，又出现了N（0≤N≤50,000）个岩石，每个岩石与起点的距离为整数Di（0＜Di＜L）。

为了玩游戏，每头牛依次从起点的岩石开始，试图在终点的岩石上到达终点，只在岩石之间跳跃。当然，不那么灵活的牛永远也到不了最后的岩石，而是在河里结束。

农场主约翰为他的奶牛感到骄傲，每年都会观看这一活动。但随着时间的推移，他厌倦了看着其他农场主的胆小的奶牛一瘸一拐地走过那些放在一起太近的岩石之间的短距离。
他计划移走几块石头，以增加奶牛必须跳过的最短距离，从而到达终点。他知道他不能移除起点和终点的岩石，但他计算出他有足够的资源来移除最多M块岩石（0≤M≤N）。

FJ想知道，在他开始移走石头之前，他到底能增加多少最短的距离*。请帮助农夫约翰确定在移走最佳的M块石头后，牛要跳的最大可能的最短距离。

输入

第1行。三个隔开空间的整数。L，N，和M
第2...N+1行：每行包含一个整数，表示某个石头离起始石头有多远。没有两块石头有相同的位置。
输出

第1行。一个单一的整数，是牛在移走M个石头后要跳的最短距离的最大值。
输入样本
25 5 2
2
14
11
21
17
样本输出
4

温馨提示
在移除任何石头之前，最短的跳跃是从0（开始）到2的跳跃。在移除2和14的石头之后，所需的最短跳跃是4的跳跃（从17到21或者从21到25）。


*/


const int N = 50010;
int stone[N];
int L, n, m;

bool check(int x) {
	int curr = 0; int rmnum = 0;
	for (int i = 0; i < n; i++) {
		if (stone[i] - curr < x) {
			rmnum++;
		}
		else {
			curr = stone[i];
		}
	}

	if (L - curr < x) {
		rmnum++;
	}

	if (rmnum <= m) {
		return true;
	}

	return false;
 }

int main()
{
	cin >> L >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> stone[i];
	}
	sort(stone, stone+n);
	int l = 0; int r = L+1;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid-1;
	}

	cout << l << endl;

	return 0;
}

 